package com.cskaoyan.javase.recursion._0introduction;

/**
 * 递归:
 * 在一个故事当中，再次提到了同样的故事，那么这种类似 "套娃"的理念，其实就是递归（recursion）的核心理念。
 *
 * 递归的定义:
 * 我们把方法在运行时调用自身的情况，称之为递归，又叫做递归调用。
 *
 * 如何写一个递归呢?
 * 1.首先需要在方法体中写自身调用自身的语句,称之为"递归体"
 *      递归体对于递归而言是必不可少的
 *
 * 2.一个递归如果仅有递归体,就一定会栈溢出,所以为了避免栈溢出
 *      需要给出一个条件 让方法出栈,停止递归
 *      这种递归停止的条件,称之为"递归的出口"
 *      合法的递归,"递归的出口"必不可少
 *
 * 3.一个递归,有递归体,有递归的出口,就一定是安全的吗?
 * 就一定不出问题吗?
 * 当然不是
 * 即便是有出口的递归，递归的深度(次数)也不能超过栈空间的大小，否则仍然会报错。
 *
 *总结:
 *      递归是一个非常危险的语法,稍有不慎就有可能栈溢出错误
 *      所以实际开发中,碰到一个问题,非常不建议大家使用递归求解(只有当万不得已,才考虑使用递归)
 *
 * @since 10:46
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        /*
            分析一下这个程序执行的结果是什么呢?
            sum(10) = 10 + sum(9);
            sum(9) = 9 + sum(8);
            sum(8) = 8 + sum(7);
            ...
            以上过程是不可能自己停下来的,所以:
                1.死循环
                2.报错终止
                3.电脑炸了(绝不可能)

            实际上直接运行这样的代码会导致程序报错 终止执行
            抛出了异常: StackOverflowError(栈溢出错误)
            栈: 指的是JVM栈
            这里是因为栈内存空间不足,溢出,导致的错误

            为什么呢?为什么会栈溢出呢?
            Method 'sum()' recurses infinitely, and can only end by throwing an exception
            因为方法只进栈 不出栈 就会导致栈内存不足,栈溢出

            怎么解决呢?
            之所以栈溢出是因为方法栈帧只进不出
            所以方法需要出栈来避免栈溢出
            需要给出一个条件让方法执行完毕,终止递归

            有递归出口后
            sum(10) = 55
            sum(100) = 5050
         */
        System.out.println(sum(10000));
    }

    // 需求: 递减求和
    public static long sum(int num) {
        // 递归的出口
        if (num == 0) {
            return 0;
        }
        // 递归体
        return num + sum(num - 1);
    }
}
